package org.example.leetcode.addon.lc113;

import org.example.util.TreeNode;

import java.util.*;

public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;

        Deque<TreeNode> nodes = new LinkedList<>();
        Deque<List<Integer>> paths = new LinkedList<>();
        nodes.push(root);
        List<Integer> rootPath = new ArrayList<>();
        rootPath.add(root.val);
        paths.push(rootPath);

        while (!nodes.isEmpty()) {
            TreeNode node = nodes.pop();
            List<Integer> path = paths.pop();

            if (node.left == null && node.right == null && node.val == targetSum) {
                ans.add(path);
            }

            if (node.left != null) {
                nodes.push(node.left);

                path.add(node.left.val);
                paths.push(new ArrayList<>(path));
                node.left.val += node.val;
                path.remove(path.size() - 1);
            }

            if (node.right != null) {
                nodes.push(node.right);

                path.add(node.right.val);
                paths.push(new ArrayList<>(path));
                node.right.val += node.val;

            }
        }

        return ans;
    }

}
